class Solution {
public:
    vector<vector<int>> rst;
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums;
        combinationSum3Step(nums, k, n);
        return rst;
    }

    void combinationSum3Step(vector<int> &nums, int k,  int n){
        if(nums.size() == k){
            if(n == 0) rst.push_back(nums);
            return;
        }

        for(int i = nums.empty() ? 1 : nums[nums.size() - 1] + 1; i <= 9; ++i){
            nums.push_back(i);
            combinationSum3Step(nums, k, n - i);
            nums.pop_back();
        }
    }
};